{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Structural Imbalance with the D-Wave System"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import random\n",
    "from dwave.system.samplers import DWaveSampler\n",
    "from dwave.system.composites import EmbeddingComposite\n",
    "import dwave_networkx as dnx\n",
    "from helpers.draw import draw\n",
    "from dwave_structural_imbalance_demo.mmp_network.loader import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Formulating the Problem for a D-Wave System"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "D-Wave systems solve Ising problems: given $N$ variables $s_1,...,s_N$, where each variable $s_i$ can have values $-1$ or $+1$, the system finds assignments of values that minimize \n",
    "\n",
    "  $\\sum_{i=1}^N h_i s_i +\n",
    "  \\sum_{i<j}^N J_{i,j} s_i s_j$,\n",
    "\n",
    "where $h_i$ and $J_{i,j}$ are configurable (linear and quadratic) coefficients.\n",
    "\n",
    "In our case, variables $s_i$ can represent people, with values $-1,+1$ denoting a person's assignment to one of the two sets we want to divide the social network into. If we set $J_{i,j}$ to $-1$ for friendly $s_is_j$ pairs and $+1$ for hostile pairs, their multiplication takes values\n",
    "\n",
    "$J_{i,j} s_i s_j=\n",
    "\\begin{cases} \n",
    "      -1 & \\text{friends in same set (} s_i=s_j \\text{) or enemies in different sets ($s_i \\ne s_j$)} \\\\\n",
    "      +1 & \\text{friends in different sets ($s_i \\ne s_j$) or enemies in same set ($s_i=s_j$)} \n",
    "\\end{cases}\n",
    "$\n",
    "\n",
    "The summation $\\sum_{i<j}^N J_{i,j} s_i s_j$ now decrements when an assignment contributes to balance and increments when it contributes to frustration.\n",
    "\n",
    "The quantum computer finds partitions (assignments of $s_i$) that minimize frustration."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A Real-World Example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A study of the violent extremist network in Syria found that the network was balanced in 2012. However, in 2013 an increase in active groups in the Syrian theatre changed the existing landscape significantly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sampler = EmbeddingComposite(DWaveSampler(endpoint='https://cloud.dwavesys.com/sapi', \\\n",
    "                                          token='put_here_your_token', \\\n",
    "                                          solver='DW_2000Q_2_1'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = global_signed_social_network()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Select the Syria subregion by creating subgraph S from the full data set G\n",
    "syria_groups = set()\n",
    "for v, data in G.nodes(data=True):\n",
    "    if 'map' not in data:\n",
    "        continue\n",
    "    if data['map'] in {'Syria', 'Aleppo'}:\n",
    "        syria_groups.add(v)\n",
    "S = G.subgraph(syria_groups)\n",
    "\n",
    "# Filter by year\n",
    "year = 2013\n",
    "filtered_edges = ((u, v) for u, v, a in S.edges(data=True) if a['event_year'] <= year)\n",
    "S = S.edge_subgraph(filtered_edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "position = draw(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Return a good partition of the Syrian 2013 network and its frustrated edges \n",
    "imbalance, bicoloring = dnx.structural_imbalance(S, sampler)\n",
    "# Annotate the network with the returned frustrated edges and node sets\n",
    "for edge in S.edges:\n",
    "    S.edges[edge]['frustrated'] = edge in imbalance\n",
    "for node in S.nodes:\n",
    "    S.nodes[node]['color'] = bicoloring[node]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Redraw the network with the previous node positioning: nodes are now bicolored and dashed lines indicate frustrated edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "draw(S, position);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Redraw the network with a new positioning that separates the two sets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Frustrated edges now stand out\n",
    "draw(S);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What about a classical graph algorithm?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import dimod\n",
    "solver = dimod.ExactSolver()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Return a good partition of the Syrian 2013 network and its frustrated edges \n",
    "imbalance, bicoloring = dnx.structural_imbalance(G, solver)\n",
    "# Annotate the network with the returned frustrated edges and node sets\n",
    "for edge in S.edges:\n",
    "    S.edges[edge]['frustrated'] = edge in imbalance\n",
    "for node in S.nodes:\n",
    "    S.nodes[node]['color'] = bicoloring[node]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
